package msb.class02;

import org.junit.Assert;
import org.junit.Test;
import common.util.ArrayUtil;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 需求:
 * 数组实现队列和栈
 * <p>
 * 实现：
 * 队列： ring_array
 */
public class Code05_QueueAndStackWithArray {

    @Test
    public void testQueue() {
        int[] instant = ArrayUtil.instant(100, 100);
        QueueWithArray queueWithArray = new QueueWithArray(instant.length);
        Queue<Integer> linkedList = new LinkedList();
        for (Integer e : instant) {
            queueWithArray.add(e);
            linkedList.add(e);
        }

        for (int e : instant) {
            Integer poll1 = queueWithArray.poll();
            Integer poll2 = linkedList.poll();
            Assert.assertEquals(poll1.intValue(), poll2.intValue());
        }
    }

    @Test
    public void testStack() {
        int[] instant = ArrayUtil.instant(100, 100);
        StackWithArray stackWithArray = new StackWithArray(100);
        Stack<Integer> stack = new Stack();
        for (Integer e : instant) {
            stackWithArray.add(e);
            stack.add(e);
        }

        for (int e : instant) {
            Integer poll1 = stackWithArray.pop();
            Integer poll2 = (Integer) stack.pop();
            Assert.assertEquals(poll1.intValue(), poll2.intValue());
        }
    }

    public static class StackWithArray {
        public int[] array;
        public int maxSize;
        public int size;

        public StackWithArray(int maxSize) {
            this.array = new int[maxSize];
            this.maxSize = maxSize;
            this.size = 0;
        }

        public boolean add(Integer e) {
            if (maxSize == size) {
                throw new RuntimeException();
            }
            array[size] = e;
            size++;
            return true;
        }

        public Integer pop() {
            if (size == 0) {
                throw new RuntimeException();
            }
            size--;
            return array[size];
        }
    }

    public static class QueueWithArray {
        public int[] array;
        public int maxSize;
        public int size;
        public int head;

        public QueueWithArray(int maxSize) {
            this.array = new int[maxSize];
            this.maxSize = maxSize;
            this.size = 0;
            this.head = 0;
        }

        public boolean add(Integer e) {
            if (maxSize == size) {
                throw new RuntimeException();
            }
            array[head + size] = e;
            size++;
            return true;
        }

        public Integer poll() {
            if (size == 0) {
                throw new RuntimeException();
            }
            int result = array[head];
            head = (head + 1 % maxSize);
            return result;
        }

    }
}